package leetcode;

import java.util.*;

// (贪心算法）
public class Demo8 {


    //860. 柠檬水找零
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int x : bills) {
            if (x == 5) {
                five++;
            } else if (x == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (five != 0 && ten != 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }


    //2208. 将数组和减半的最少操作次数
    public int halveArray(int[] nums) {
        double sum = 0, cur = 0;
        PriorityQueue<Double> q = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
        for (int x : nums) {
            q.add((double) x);
            sum += x;
        }

        int step = 0;
        while (cur < sum / 2.0) {
            step++;
            Double t = q.poll() / 2.0;
            cur += t;
            q.add(t);
        }
        return step;
    }


    //179. 最大数
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (o1, o2) -> {
            return (o2 + o1).compareTo(o1 + o2);
        });

        StringBuilder ret = new StringBuilder();
        for (String s : strs) ret.append(s);
        if (ret.charAt(0) == '0') return "0";
        return ret.toString();
    }


    //376. 摆动序列
    public int wiggleMaxLength(int[] nums) {
        int left = 0, ret = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int right = nums[i + 1] - nums[i];
            if (right == 0) continue;
            if (left * right <= 0) {
                ret++;
                left = right;
            }
        }
        return ret + 1;
    }




    //300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // 贪心解法
        int n = nums.length, len = 0;
        int[] arr = new int[n];

        for(int i = 0; i < n; i++) {
            if(len == 0 || nums[i] > arr[len - 1]) {
                arr[len++] = nums[i];
            } else {
                int index = binSearch(arr, 0, len - 1, nums[i]);
                if(arr[index] >= nums[i]) arr[index] = nums[i];
            }
        }
        return len;
    }
    public int binSearch(int[] arr, int left, int right, int val) {
        int mid;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(arr[mid] < val) left = mid + 1;
            else right = mid;
        }
        return left;
    }



    //334. 递增的三元子序列
    public boolean increasingTriplet(int[] nums) {
        // 贪心解法
        int n = nums.length, a = nums[0], b = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            if(nums[i] > b) return true;
            else if(nums[i] > a) b = nums[i];
            else a = nums[i];
        }
        return false;
    }



    //674. 最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        int left = 0, right = 1, len = 1;
        while(right < nums.length) {
            while(right < nums.length && nums[right] > nums[right - 1]) right++;
            len = Math.max(len, right - left);
            left = right++;
        }
        return len;
    }




    //121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int min = 10001, ret = 0;
        for(int x : prices) {
            if(x <= min) min = x;
            else ret = Math.max(ret, x - min);
        }
        return ret;
    }




    //122. 买卖股票的最佳时机 II
    public int maxProfit2(int[] prices) {
        int ret = 0, n = prices.length;
        for(int i = 0; i < n - 1; i++) {
            if(prices[i + 1] > prices[i]) ret += prices[i + 1] - prices[i];
        }
        return ret;
    }



    //1005. K 次取反后最大化的数组和
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            if(k > 0) {
                if(nums[i] < 0) nums[i] = -nums[i];
                else if(k % 2 == 0) k = 0;
                else {
                    if(i > 0 && nums[i - 1] < nums[i]) ret -=  2 * nums[i - 1];  // 前一个数比较小，要减去2倍这个数
                    else nums[i] = -nums[i];
                }
                k--;
            }
            ret += nums[i];
        }
        // 原数组中全是负数，且k为奇数，减去2倍最后一个数
        if(k > 0 && k % 2 == 1) ret -= 2 * nums[nums.length - 1];
        return ret;
    }




    //2418. 按身高排序
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] arr = new Integer[n];
        for(int i = 0; i < n; i++) arr[i] = i;
        Arrays.sort(arr, (o1, o2) -> heights[o2] - heights[o1]);

        String[] ret = new String[n];
        for(int i = 0; i < n; i++) ret[i] = names[arr[i]];
        return ret;
    }



    //870. 优势洗牌
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Arrays.sort(nums1);
        Integer[] index = new Integer[n];
        for(int i = 0; i < n; i++) index[i] = i;
        Arrays.sort(index, (o1, o2) -> nums2[o1] - nums2[o2]);// 将nums2 中的数的大小从小到大进行排序，但存放值为下标

        // 田忌赛马
        int[] ret = new int[n];
        int left = 0, right = n - 1;
        for(int x : nums1) {
            if(x <= nums2[index[left]]) {
                ret[index[right--]] = x;
            } else {
                ret[index[left++]] = x;
            }
        }
        return ret;
    }



    //409. 最长回文串
    public int longestPalindrome(String s) {
        Map<Character, Integer> hash = new HashMap<>();
        for(char ch : s.toCharArray()) {
            hash.put(ch, hash.getOrDefault(ch, 0) + 1);
        }

        int ret = 0;
        for(Integer x : hash.values()) {
            ret += x / 2 * 2;
        }
        if(ret < s.length()) ret++;
        return ret;
    }




    //942. 增减字符串匹配
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] ret = new int[n + 1];
        int left = 0, right = n, k = 0;

        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == 'I') ret[k++] = left++;
            else ret[k++] = right--;
        }
        ret[k] = left;
        return ret;
    }




    //455. 分发饼干
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int count = 0;
        for(int i = 0, j = 0; i < g.length && j < s.length; i++, j++) {
            while(j < s.length && s[j] < g[i]) j++;
            if(j < s.length) {
                count++;
            }
        }
        return count;
    }





    //553. 最优除法
    public String optimalDivision(int[] nums) {
        StringBuffer ret = new StringBuffer();
        int n = nums.length;
        ret.append(nums[0]);
        if(n == 2) {
            ret.append("/" + nums[1]);
        } else if(n > 2) {
            ret.append("/(");
            for(int i = 1; i < n; i++) {
                ret.append(nums[i]);
                if(i < n - 1) ret.append('/');
            }
            ret.append(')');
        }
        return ret.toString();
    }




    //55. 跳跃游戏
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n == 1) return true;
        int left = 0, right = 0, nextRight = 0;

        while(left <= right) {
            for(; left <= right; left++) {
                if(left + nums[left] >= n - 1) return true;
                nextRight = Math.max(nextRight, left + nums[left]);
            }
            left = right + 1;
            right = nextRight;
        }
        return false;
    }




    //45. 跳跃游戏 II
    public int jump(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;

        int left = 0, right = 0, ret = 0;
        while(right < n) {
            int nextRight = 0;
            for(; left <= right; left++) {
                if(left + nums[left] >= n - 1) return ret + 1;
                else if(left + nums[left] > nextRight) nextRight = left + nums[left];
            }
            ret++;
            left = right + 1;
            right = nextRight;
        }
        return -1;
    }




    //134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        for(int i = 0; i < n; i++) {
            if(gas[i] - cost[i] < 0) continue;

            int rest = 0, step = 0;
            for(; step < n; step++) {
                int index = (i + step) % n;
                rest += gas[index] - cost[index];
                if(rest < 0) break;
            }
            if(step == n) return i;      // 找到正确的出发位置
            i += step;
        }
        return -1;
    }



    //738. 单调递增的数字
    public int monotoneIncreasingDigits(int n) {
        if(n < 10) return n;
        char[] num = Integer.toString(n).toCharArray();
        int i = 0, len = num.length;
        while(i < len - 1 && num[i] <= num[i + 1]) i++;
        if(i == len - 1) return n;      // 此时该数即为递增数

        // 回退操作：可能操作多个相同的数字
        while(i > 0 && num[i] == num[i - 1]) i--;
        num[i]--;

        for(int k = i + 1; k < len; k++) num[k] = '9';
        return Integer.parseInt(new String(num));
    }


    // 397. 整数替换
    public int integerReplacement(int n) {
        if (n == 1) return 0;
        int res = 0;
        long num = n;
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                int mod = (int)num % 4;
                if (num == 3 || mod == 1) {
                    num -= 1;
                } else {
                    num += 1;
                }
            }
            res++;
        }
        return res;
    }



    // 354. 俄罗斯套娃信封问题
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });

        // 寻找最长递增子序列
        List<Integer> list = new ArrayList<>();
        list.add(envelopes[0][1]);
        int n = envelopes.length;
        for (int i = 1; i < n; i++) {
            int h = envelopes[i][1], sz = list.size();
            if (h > list.get(sz - 1)) {
                list.add(h);
            } else {
                int left = 0, right = sz - 1, mid = 0;
                while (left < right) {
                    mid = left + (right - left) / 2;
                    if (list.get(mid) < h) left = mid + 1;
                    else right = mid;
                }
                list.set(left, h);
            }
        }
        return list.size();
    }


    // 767. 重构字符串
    public String reorganizeString(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int[] count = new int[26];
        // 1. 统计每个字母出现的次数
        for (char ch : arr) {
            count[ch - 'a']++;
        }
        // 2. 统计出现次数最多的字符
        int max = 0;
        char ch = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > max) {
                max = count[i];
                ch = (char)('a' + i);
            }
        }
        // 若 max > (n + 1) / 2,则一定不能重排
        if (max > (n + 1) / 2) return "";

        // 3. 优先排序出现次数最多的字符
        int j = 0;
        char[] ret = new char[n];
        for (int i = 0; i < n; i += 2) {
            ret[i] = ch;
            if (--count[ch - 'a'] == 0) {
                while (j < 26 && count[j] == 0) j++;
                ch = (char)('a' + j);
            }
        }
        for (int i = 1; i < n; i += 2) {
            ret[i] = ch;
            if (--count[ch - 'a'] == 0) {
                while (j < 26 && count[j] == 0) j++;
                ch = (char)('a' + j);
            }
        }
        return new String(ret);
    }



    // 1054. 距离相等的条形码
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] count = new int[10001];
        for (int x : barcodes) {
            count[x]++;
        }

        // 统计出现次数最多的数字
        int max = 0, index = 0;
        for (int i = 1; i <= 10000; i++) {
            if (count[i] > max) {
                max = count[i];
                index = i;
            }
        }

        // 优先排序出现次数最多的数字
        int n = barcodes.length, cur = 1; // cur 出现数字的下标
        int[] ret = new int[n];
        for (int i = 0; i < n; i += 2) {
            ret[i] = index;
            if (--count[index] == 0) {
                while (cur <= n && count[cur] == 0) cur++;
                index = cur;
            }
        }
        for (int i = 1; i < n; i += 2) {
            ret[i] = index;
            if (--count[index] == 0) {
                while (cur <= n && count[cur] == 0) cur++;
                index = cur;
            }
        }
        return ret;
    }



    // 1262. 可被三整除的最大和
    public int maxSumDivThree(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 3 == 0) return sum;

        // 如果 sum % 3 == 1,则可能存在1个 num % 3 == 1 或 2个 num % 3 == 2
        final int INF = 0x3f3f3f3f;
        if (sum % 3 == 1) {
            int x = INF, y1 = INF, y2 = INF;
            for (int num : nums) {
                if (num % 3 == 1 && num < x) x = num;
                else if (num % 3 == 2) {
                    if (num < y1) {
                        y2 = y1;
                        y1 = num;
                    } else if (num <= y2){
                        y2 = num;
                    }
                }
            }
            sum = Math.max(sum - x, sum - y1 - y2);
        } else {
            // 如果 sum % 3 == 2,则可能存在2 个 num % 3 == 1 或 1个 num % 3 == 2
            int x1 = INF, x2 = INF, y = INF;
            for (int num : nums) {
                if (num % 3 == 2 && num < y) y = num;
                else if (num % 3 == 1) {
                    if (num < x1) {
                        x2 = x1;
                        x1 = num;
                    } else if (num <= x2){
                        x2 = num;
                    }
                }
            }
            sum = Math.max(sum - x1 - x2, sum - y);
        }
        return sum;
    }



}
